﻿/************************************************************
*
* 命名空间：Deep.Algorithm.Sorting
* 文件名称：InsertionSort.cs
* 创建者：王嘉庆
* 创建日期：2021-05-28 07:00:06
* 邮箱：1101202419@qq.com
* 博客：https://blog.csdn.net/wuxinwudai
* 功能描述：
* 使用说明：
* 最后更新日期：
*************************************************************/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Deep.Algorithm.Sorting
{
    /// <summary>
    /// 插入排序，稳定算法，时间复杂度 O(n^2)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class InsertionSort : SortAlgorithm
    {
        public override T[] Sort<T>(T[] arr)
        {
            for (int i = 1; i < arr.Length; i++)
            {
                for (int j = i; j >0 ; j--)
                {
                    if (arr[j-1].CompareTo(arr[j]) > 0)
                    {
                        Exchange(arr,j-1,j);
                    }
                    else
                    {
                        break;
                    }
                }
            }
            return arr;
        }
    }
}
